import java.math.BigInteger;

public class ProductAndSum {
	private static final int MOD = 500500573;

	private long[] f;
	private long[] of;
	private long[] st;

	public int getSum(int p2, int p3, int p5, int p7, int S) {
		f = new long[S + 1];
		of = new long[S + 1];
		long[] t = new long[S + 1];
		st = new long[S + 1];
		f[0] = 1;
		of[0] = 1;
		t[0] = 1;
		st[0] = 1;
		for (int i = 1; i <= S; i++) {
			f[i] = (f[i - 1] * i) % MOD;
			of[i] = BigInteger.valueOf(f[i]).modInverse(BigInteger.valueOf(MOD)).longValue();
			t[i] = (t[i - 1] * 10) % MOD;
			st[i] = (st[i - 1] + t[i]) % MOD;
		}
		return account5(p2, p3, p5, p7, S, new int[10]);
	}

	private int account5(int p2, int p3, int p5, int p7, int s, int[] d) {
		d[5] = p5;
		s -= 5 * p5;
		return account7(p2, p3, p7, s, d);
	}

	private int account7(int p2, int p3, int p7, int s, int[] d) {
		if (s < 0)
			return 0;
		d[7] = p7;
		s -= 7 * p7;
		return account9(p2, p3, s, d);
	}

	private int account9(int p2, int p3, int s, int[] d) {
		if (s < 0)
			return 0;
		long result = 0;
		for (int i = Math.min(p3 / 2, s / 9); i >= 0; i--) {
			d[9] = i;
			result += account6(p2, p3 - 2 * i, s - 9 * i, d);
		}
		return (int) (result % MOD);
	}

	private int account6(int p2, int p3, int s, int[] d) {
		long result = 0;
		for (int i = Math.min(s / 6, Math.min(p3, p2)); i >= 0; i--) {
			d[6] = i;
			result += account3(p2 - i, p3 - i, s - 6 * i, d);
		}
		return (int) (result % MOD);
	}

	private int account3(int p2, int p3, int s, int[] d) {
		d[3] = p3;
		s -= 3 * p3;
		return account8(p2, s, d);
	}

	private int account8(int p2, int s, int[] d) {
		if (s < 0)
			return 0;
		long result = 0;
		for (int i = Math.min(s / 8, p2 / 3); i >= 0; i--) {
			d[8] = i;
			result += account4(p2 - 3 * i, s - 8 * i, d);
		}
		return (int) (result % MOD);
	}

	private int account4(int p2, int s, int[] d) {
		long result = 0;
		for (int i = Math.min(s / 4, p2 / 2); i >= 0; i--) {
			d[4] = i;
			result += account2(p2 - 2 * i, s - 4 * i, d);
		}
		return (int) (result % MOD);
	}

	private int account2(int p2, int s, int[] d) {
		d[2] = p2;
		s -= p2 * 2;
		if (s < 0)
			return 0;
		d[1] = s;
		int numDigits = 0;
		for (int i : d)
			numDigits += i;
		long c = f[numDigits - 1];
		for (int i = 0; i < 10; i++) {
			c = (c * of[d[i]]) % MOD;
		}
		long result = 0;
		for (int i = 0; i < 10; i++)
			result += ((c * st[numDigits - 1]) % MOD) * i * d[i];
		return (int) (result % MOD);
	}


	// BEGIN CUT HERE
	public static void main(String[] args) {
		if (args.length == 0) {
			ProductAndSumHarness.run_test(-1);
		} else {
			for (int i=0; i<args.length; ++i)
				ProductAndSumHarness.run_test(Integer.valueOf(args[i]));
		}
	}
// END CUT HERE
}

// BEGIN CUT HERE
class ProductAndSumHarness {
	public static void run_test(int casenum) {
		if (casenum != -1) {
			if (runTestCase(casenum) == -1)
				System.err.println("Illegal input! Test case " + casenum + " does not exist.");
			return;
		}
		
		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = runTestCase(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}
		
		if (total == 0) {
			System.err.println("No test cases run.");
		} else if (correct < total) {
			System.err.println("Some cases FAILED (passed " + correct + " of " + total + ").");
		} else {
			System.err.println("All " + total + " tests passed!");
		}
	}
	
	static boolean compareOutput(int expected, int result) { return expected == result; }
	static String formatResult(int res) {
		return String.format("%d", res);
	}
	
	static int verifyCase(int casenum, int expected, int received) { 
		System.err.print("Example " + casenum + "... ");
		if (compareOutput(expected, received)) {
			System.err.println("PASSED");
			return 1;
		} else {
			System.err.println("FAILED");
			System.err.println("    Expected: " + formatResult(expected)); 
			System.err.println("    Received: " + formatResult(received)); 
			return 0;
		}
	}

	static int runTestCase(int casenum) {
		switch(casenum) {
		case 0: {
			int p2                    = 2;
			int p3                    = 0;
			int p5                    = 0;
			int p7                    = 0;
			int S                     = 4;
			int expected__            = 26;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}
		case 1: {
			int p2                    = 0;
			int p3                    = 0;
			int p5                    = 0;
			int p7                    = 0;
			int S                     = 10;
			int expected__            = 110109965;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}
		case 2: {
			int p2                    = 2;
			int p3                    = 0;
			int p5                    = 0;
			int p7                    = 0;
			int S                     = 5;
			int expected__            = 610;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}
		case 3: {
			int p2                    = 1;
			int p3                    = 1;
			int p5                    = 1;
			int p7                    = 1;
			int S                     = 10;
			int expected__            = 0;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}
		case 4: {
			int p2                    = 5;
			int p3                    = 5;
			int p5                    = 5;
			int p7                    = 5;
			int S                     = 100;
			int expected__            = 61610122;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}

		// custom cases

/*      case 5: {
			int p2                    = ;
			int p3                    = ;
			int p5                    = ;
			int p7                    = ;
			int S                     = ;
			int expected__            = ;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}*/
/*      case 6: {
			int p2                    = ;
			int p3                    = ;
			int p5                    = ;
			int p7                    = ;
			int S                     = ;
			int expected__            = ;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}*/
/*      case 7: {
			int p2                    = ;
			int p3                    = ;
			int p5                    = ;
			int p7                    = ;
			int S                     = ;
			int expected__            = ;

			return verifyCase(casenum, expected__, new ProductAndSum().getSum(p2, p3, p5, p7, S));
		}*/
		default:
			return -1;
		}
	}
}

// END CUT HERE
